package course;

import java.util.Arrays;
import java.util.function.Consumer;

public class Sort {
    public static void main(String[] args) {
        SortChecker.checkSort(QuickSortTest::myQuickSortTest, 1000, 100, 1, false);
    }
}


// 快速排序3.0
class QuickSortTest{
    public static void myQuickSortTest(int arr[]){
        if(arr == null || arr.length < 2)
            return;
        QuickSort(arr, 0, arr.length - 1);
    }
    
    private static void QuickSort(int[] arr, int L, int R){
        if(L >= R)
            return;
        int[] res = QuickSortCore(arr, L, R);
        QuickSort(arr,L, res[0] - 1);
        QuickSort(arr, res[1] + 1, R);
    }

    private static int[] QuickSortCore(int[] arr, int L, int R){
        swap(arr, (int)(L + Math.random() * (R - L + 1)), R);

        int num = arr[R];
        int less = L, more = R;
        while(L < more){
            if(arr[L] < num){
                swap(arr, less++, L++);
            }else if(arr[L] > num){
                arr[more--]=arr[L];
                arr[L] = arr[more];
            }else{
                L++;
            }
        }
        arr[more] = num;
        return new int[]{less, more};
    }

    public static void swap(int[] arr, int indexA, int indexB){
        if(indexA == indexB) return;
        arr[indexA] = arr[indexA] ^ arr[indexB];
        arr[indexB] = arr[indexA] ^ arr[indexB];
        arr[indexA] = arr[indexA] ^ arr[indexB];
    }
}


class MergeSortTest{
    /*归并排序
     * 没有浪费比较行为
     */
    public static void myMergeSort(int[] arr){
        if(arr == null || arr.length <= 1)
            return;
        mergeSort(arr, 0, arr.length - 1);
    }
    
    public static void mergeSort(int[] arr, int L, int R){
        if(L == R)
            return;
        int mid = L + ((R - L) >> 1);
        mergeSort(arr, L, mid);
        mergeSort(arr, mid + 1, R);
        mergeSortCore(arr, L, mid, R);
    }

    private static void mergeSortCore(int[] arr, int L, int mid, int R){
        int left = L, right = mid + 1, index = 0;
        int[] tempArr = new int[R - L + 1];
        while(left <= mid && right <= R){
            tempArr[index++] = arr[left] <= arr[right] ? arr[left++] : arr[right++];
        }
        while(left <= mid){
            tempArr[index++] = arr[left++];
        }
        while(right <= R){
            tempArr[index++] = arr[right++];
        }
        for(int i = 0; i < tempArr.length; i++){
            arr[L + i] = tempArr[i];
        }
    }
}


class SortChecker {
    /**
     * 对数器方法
     * @param sorter  你要验证的排序方法 (例如 MyClass::mySort)
     * @param testTime  验证次数
     * @param maxSize   数组最大长度
     * @param maxValue  数组元素最大值
     * @param allowNegative 是否允许负数
     */
    public static void checkSort(Consumer<int[]> sorter, int testTime, int maxSize, int maxValue, boolean allowNegative) {
        boolean success = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue, allowNegative);
            int[] arr2 = Arrays.copyOf(arr1, arr1.length);
            int[] arr3 = Arrays.copyOf(arr1, arr1.length);

            sorter.accept(arr1);     // 你的排序
            Arrays.sort(arr2);       // 系统排序

            if (!Arrays.equals(arr1, arr2)) {
                success = false;
                System.out.println("❌ 出错了！");
                System.out.println("原始数组: " + Arrays.toString(arr3));
                System.out.println("你的排序结果: " + Arrays.toString(arr1));
                System.out.println("系统排序结果: " + Arrays.toString(arr2));
                break;
            }
        }
        System.out.println(success ? "所有测试通过！" : "测试失败！");
    }

    public static void checkSort(Consumer<int[]> sorter, int testTime){
        checkSort(sorter, testTime, 10000, 10000, true);
    }

    public static void checkSort(Consumer<int[]> sorter, int testTime, int maxSize, int maxValue){
        checkSort(sorter, testTime, maxSize, maxValue, true);
    }

    // 生成随机数组
    private static int[] generateRandomArray(int maxSize, int maxValue, boolean allowNegative) {
        int size = (int)(Math.random() * (maxSize + 1));
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            int value = (int)(Math.random() * (maxValue + 1));
            if (allowNegative) {
                value -= (int)(Math.random() * (maxValue + 1));
            }
            arr[i] = value;
        }
        // System.out.println(Arrays.toString(arr));
        return arr;
    }
}